// https://leetcode.cn/problems/shortest-completing-word/
// Created by ade on 2022/8/16.
//
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector <string> &words) {
        string plt = getPlate(licensePlate);
        int pLen = plt.size();
        int maxJ = 0; // 权重
        int minS = 0; // 权重
        string res = "";
        for (auto word : words) {
            string wordS = word;
            sort(wordS.begin(), wordS.end());
            int i = 0;
            int j = 0;
            while (i < word.size()) {
                if (j >= pLen) break;
                if (plt[j] == wordS[i]) {
                    j++;
                }
                i++;
            }
            if (j > maxJ) {
                maxJ = j;
                minS = word.size();
                res = word;
            } else if (j == maxJ && minS > word.size()) {
                minS = word.size();
                res = word;
            }
        }
        return res;
    }

    string getPlate(const string &licensePlate) {
        string plt = "";
        for (auto i : licensePlate) {
            if (i >= 'a' && i <= 'z') {
                plt += i;
            }
            if (i >= 'A' && i <= 'Z') {
                plt += (i + 32);
            }
        }
        sort(plt.begin(), plt.end());
        return plt;
    }
};

// "1s3 456"
//["looks","pest","stew","show"]

int main() {
    Solution so;
    string licensePlate = "1s3 456";
    vector <string> words = {"looks", "pest", "stew", "show"};
    string a = so.shortestCompletingWord(licensePlate, words);
    cout << a << endl;
    return 0;
}